package com.ting.test.algorithms.堆;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1
 * 返回线段最多重合区域中，包含了几条线段
 * <p>
 * 思路:
 * 先将线段按照开始位置由大到小排序
 * 创建一个小根堆
 * 将排序后的线段，入堆，入堆的条件为：
 * 1. 判断当前的堆中有没有比当前线段的开始位置小的，如果有则弹出
 * 2. 当堆中没有比当前线段小的元素时，将当前线段的结尾入堆
 * 3.当前堆中存在的元素个数，就是当前线段最多的重合区域个数
 */
public class 最大线段重合问题2 {
    public static void main(String[] args) {
        int arr[][] = new int[][]{{1, 3}, {1, 6}, {2, 4}};
        int result = func(arr);
        System.out.println(result);
    }

    private static int func(int[][] arr) {

        ArrayList<Line> lines = new ArrayList<Line>();
        for (int[] temp : arr) {
            lines.add(new Line(temp[0], temp[1]));
        }
        lines.sort(new LineComparator());

        PriorityQueue<Integer> queue = new PriorityQueue();//小根堆


        int max = 0;
        for (Line line : lines) {
            while (!queue.isEmpty() && queue.peek() < line.getStart()) {
                queue.poll();
            }
            queue.add(line.getEnd());
            max = Math.max(max, queue.size());
        }
        return max;
    }

    private static int func2(int[][] arr) {

        ArrayList<Line> lines = new ArrayList<Line>();
        for (int[] temp : arr) {
            lines.add(new Line(temp[0], temp[1]));
        }
        lines.sort(new LineComparator());

        Stack<Integer> stack = new Stack();//小根堆


        int max = 0;
        for (Line line : lines) {
            while (!stack.isEmpty() && stack.peek() < line.getStart()) {
                stack.pop();
            }
            stack.add(line.getEnd());
            max = Math.max(max, stack.size());
        }
        return max;
    }


    static class Line {
        int start;
        int end;

        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }
    }

    static class LineComparator implements Comparator<Line> {

        @Override
        public int compare(Line o1, Line o2) {
            return o1.start - o2.start;
        }
    }

}

